 Кибернетика
 Ю.И.Манин
 Вычислимое и невычислимое
 Москва «Советское радио» 1980

 Манин Ю.И.
 Вычислимое и невычислимое. - М.: Сов. радио, 1980. - 128 с., ил. (Кибернетика).
 45 к.
 Книга посвящена доказательству существования невычислимых функций и алгоритмически неразрешимых задач. Обсуждаются проблемы оценки сложности вычислений и алгоритмов.
 Книга будет полезна широкому кругу специалистов, занимающихся проблемами машинного перевода, искусственного интеллекта, общего использования ЭВМ.
 32.81

 Редакция кибернетической литературы

 ОГЛАВЛЕНИЕ:
 Предисловие (3).
 Введение (5).
 Глава I. Рекурсивные функции и алгоритмы (16).
 1. Интуитивная вычислимость (16).
 2. Частично рекурсивные функции (20).
 3. Образцы рекурсивности (25).
 4. Перечислимые и разрешимые множества (29).
 5. Элементы рекурсивной геометрии (39).
 6. Конструктивные объекты и алгоритмы (44).
 Глава II. Диофантовы множества и алгоритмическая неразрешимость (46).
 1. Основные результаты (46).
 2. План доказательства (49).
 3. Перечислнмые множества являются D-множествами (51).
 4. Редукция (53).
 5. Конструкция специального диофантова множества (56).
 6. График экспоненты диофантов (61).
 7. Графики факториала и биномиальных коэффициентов диофанговы (62).
 8. Дополнения (64).
 Глава III. Сложность и случайность (65).
 1. Версальные семейства (65).
 2. Сложность по Колмогорову (68).
 3. Сложность и случайность (73).
 Глава IV. Формальные языки и вычислимость (74).
 1. Арифметика синтаксиса (74).
 2. Синтаксический анализ (80).
 3. Перечислимость выводимых формул (85).
 Глава V. Теорема Геделя (87).
 1. Принцип неполноты (87).
 2. Неперечислимость истинных формул (88).
 3. О длине доказательств (91).
 4. Арифметическая иерархия (93).
 5. Продуктивность арифметической истины (96).
 6. Вычислимые функции с очень быстрым ростом (99).
 Глава VI. Рекурсивные группы (101).
 1. Основной результат и его следствия (101).
 2. Свободные произведения и HNN-расширения (104).
 3. Вложения в группы с двумя образующими (107).
 4. Хорошие подгруппы (108).
 5 Ограниченные системы образующих (111).
 6. Окончание доказательства (116).
 Список литературы (123).
 Именной указатель (125).
 Предметный указатель (125).

 Юрий Иванович Манин
 ВЫЧИСЛИМОЕ И НЕВЫЧИСЛИМОЕ